package com.c2b.algorithm.leetcode.hot100;

/**
 * <a href="https://leetcode.cn/problems/minimum-path-sum/">最小路径和</a>
 * <p>给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。<br>
 * 说明：每次只能向下或者向右移动一步。</p>
 * <pre>
 * 示例 1：
 *      输入：grid = {{1,3,1},{1,5,1},{4,2,1}}
 *      {
 *          {1   3   1}
 *          {1   5   1}
 *          {4   2   1}
 *       }
 *      输出：7
 *      解释：因为路径 1→3→1→1→1 的总和最小。
 *
 * 示例 2：
 *      输入：grid = {{1,2,3},{4,5,6}}
 *      {
 *          {1,2,3}
 *          {4,5,6}
 *      }
 *      输出：12
 *      解释：因为路径 1→2→3→6 的总和最小。
 * </pre>
 * <b>提示：</b>
 * <li>m == grid.length</li>
 * <li>n == grid{i}.length</li>
 * <li>1 <= m, n <= 200</li>
 * <li>0 <= grid{i}{j} <= 100</li>
 *
 * @author c2b
 * @since 2023/4/25 13:21
 */
public class Hot064MinPathSum {

    /**
     * <p>动态规划。</p>
     * <p>动态方程：d{m}{n} = d{m}{n} + Math.min(d{m,n-1},d{m-1}{n})</p>
     * <p>到达mn位置的路径最小和为：当前位置的路径值 + Math.min(来自上方的总路径值，来自左方的总路径值)</p>
     *
     * @param grid 网格
     * @return int 路径最小值
     */
    public int minPathSum(int[][] grid) {
        // 行
        for (int i = 0; i < grid.length; i++) {
            // 列
            for (int j = 0; j < grid[0].length; j++) {
                // 判断是不是边界
                if (i == 0 && j == 0) {
                    continue;
                }
                if (i == 0) {
                    // 上边界
                    grid[i][j] += grid[i][j - 1];
                } else if (j == 0) {
                    // 左边界
                    grid[i][j] += grid[i - 1][j];
                } else {
                    // 非边界
                    grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
                }
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }

    private int m;
    private int n;

    /**
     * 递归
     *
     * @param grid
     * @return
     */
    public int minPathSum2(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        return dsf(grid, 0, 0);
    }

    private int dsf(int[][] grid, int currRow, int currCol) {
        int currentVal = grid[currRow][currCol];
        if (currRow == m - 1 && currCol == n - 1) {
            return currentVal;
        }
        // 到达边界的情况
        if (currRow == m - 1) {
            return currentVal + dsf(grid, currRow, currCol + 1);
        }
        if (currCol == n - 1) {
            return currentVal + dsf(grid, currRow + 1, currCol);
        }
        return currentVal + Math.min(dsf(grid, currRow + 1, currCol), dsf(grid, currRow, currCol + 1));
    }


    public static void main(String[] args) {
        Hot064MinPathSum hot064MinPathSum = new Hot064MinPathSum();
        int[][] grid = new int[][]
                {
                        {3, 8, 6, 0, 5, 9, 9, 6, 3, 4, 0, 5, 7, 3, 9, 3},
                        {0, 9, 2, 5, 5, 4, 9, 1, 4, 6, 9, 5, 6, 7, 3, 2},
                        {8, 2, 2, 3, 3, 3, 1, 6, 9, 1, 1, 6, 6, 2, 1, 9},
                        {1, 3, 6, 9, 9, 5, 0, 3, 4, 9, 1, 0, 9, 6, 2, 7},
                        {8, 6, 2, 2, 1, 3, 0, 0, 7, 2, 7, 5, 4, 8, 4, 8},
                        {4, 1, 9, 5, 8, 9, 9, 2, 0, 2, 5, 1, 8, 7, 0, 9},
                        {6, 2, 1, 7, 8, 1, 8, 5, 5, 7, 0, 2, 5, 7, 2, 1},
                        {8, 1, 7, 6, 2, 8, 1, 2, 2, 6, 4, 0, 5, 4, 1, 3},
                        {9, 2, 1, 7, 6, 1, 4, 3, 8, 6, 5, 5, 3, 9, 7, 3},
                        {0, 6, 0, 2, 4, 3, 7, 6, 1, 3, 8, 6, 9, 0, 0, 8},
                        {4, 3, 7, 2, 4, 3, 6, 4, 0, 3, 9, 5, 3, 6, 9, 3},
                        {2, 1, 8, 8, 4, 5, 6, 5, 8, 7, 3, 7, 7, 5, 8, 3},
                        {0, 7, 6, 6, 1, 2, 0, 3, 5, 0, 8, 0, 8, 7, 4, 3},
                        {0, 4, 3, 4, 9, 0, 1, 9, 7, 7, 8, 6, 4, 6, 9, 5},
                        {6, 5, 1, 9, 9, 2, 2, 7, 4, 2, 7, 2, 2, 3, 7, 2},
                        {7, 1, 9, 6, 1, 2, 7, 0, 9, 6, 6, 4, 4, 5, 1, 0},
                        {3, 4, 9, 2, 8, 3, 1, 2, 6, 9, 7, 0, 2, 4, 9, 0},
                        {5, 1, 8, 8, 4, 6, 8, 5, 2, 4, 1, 6, 2, 18, 9, 7}
                };
        System.out.println(hot064MinPathSum.minPathSum(grid));
    }
}
